
print("给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标")
def twoSum(nums:list[int],target:int) -> list[int]:
    for i in range(0,len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i]+nums[j] == target:
                return [i,j]



print("给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false")
def isPalindrome(x:int)->bool:
    return str(x) == str(x)[::-1]

print("编写一个函数来查找字符串数组中的最长公共前缀")
def longestCommonPrefix(strs:list[str]) ->str:
    sorted_strs = sorted(strs,key=lambda s:len(s))
    prefix = ""
    for i in range(0,len(sorted_strs[0])):
        if len(set([s[i] for s in sorted_strs])) >1:
            return prefix
        prefix=prefix+sorted_strs[0][i]
    return prefix




print("给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效")
def isValid(strs:str)->bool:
    for i in range(0,len(strs)//2):
        strs=strs.replace("()","").replace("{}","").replace("[]","")
    return len(strs)==0

def isValid2(strs:str)->bool:
    mapping={")":"(","}":"{","]":"["}
    tem_list=[]
    for s in strs:
        if s in mapping:
            if len(tem_list) == 0:
                return False
            elif tem_list.pop() != mapping.get(s):
                return False
        else:
            tem_list.append(s)
    return len(tem_list) == 0



print("给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，"
      "返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数"
      "考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过"
      "更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要"
      "返回 k")

def removeDuplicates(nums:list[int]) -> int:
    nums2=sorted(list(set(nums)))
    for i in range(0,len(nums2)):
        nums[i]=nums2[i]
    return len(nums2)


print("给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。"
      "元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量")
def removeElement(nums:list[int],val:int)->int:
    count = nums.count(val)
    for c in range(0,count):
        nums.remove(val)
    return len(nums)



print("给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。"
      "如果 needle 不是 haystack 的一部分，则返回  -1")
def strStr(haystack:str,needle:str) -> int:
    if needle in haystack:
        return haystack.index(needle)
    return -1


print("给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置")
def searchInsert(nums:list[int],target:int) ->int:
    if target in nums:
        return nums.index(target)
    else:
        nums.append(target)
        nums.sort()
        return nums.index(target)


print("给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度")
def lengthOfLastWord(strs:str) -> int:
    return len(strs.split()[-1])

print("给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。")
def plusOne(digits:list[int]) ->list[int]:
    digits=digits[::-1]
    for i in range(0,len(digits)):
        if digits[i] ==9 and i==len(digits)-1:
            digits[i]=0
            digits.append(1)
        elif digits[i] ==9:
            digits[i]=0
        else:
            digits[i]=digits[i]+1
            break
    return digits[::-1]


print("给你一个非负整数 x ，计算并返回 x 的 算术平方根"
      "由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去")
def mySqrt(x:int) -> int:
    if x==0 or x==1:
        return x
    for i in range(0,x):
        if i**2 == x:
            return i
        elif i**2 < x  and (i+1)**2>x:
            return i


print("假设你正在爬楼梯。需要 n 阶你才能到达楼顶"
      "每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?")

def climbStairs(n:int) ->int:
    if n == 0 or n==1:
        return 1
    return climbStairs(n-1)+climbStairs(n-2)



print("删除排序链表中的重复元素"
      "给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def deleteDuplicates(head:ListNode)->ListNode:
    if head is None:
        return None
    current=head
    while current.next:
        if current.val==current.next.val:
            current.next=current.next.next
            # 之所以没加这一判断是因为当前节点和下下个节点的值还没有进行判断是否相等
            # current=current.next.next
        else:
            current=current.next
    return head





print("合并两个有序数组，合并后同样非递减"
      "给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目")
def merge(nums1:list[int],m:int,nums2:list[int],n:int) -> None:
    nums1[m:]=nums2
    nums1.sort()





print("二叉树的前序遍历")
print("二叉树的中序遍历")
print("二叉树的后序遍历")
class TreeNode:
    def __init__(self,val,left,right):
        self.val=val
        self.left=left
        self.right=right
def houxubianli(root:TreeNode)->list[int]:
    res_list=[]
    def innerbiali(node:TreeNode):
        if node is None:
            return
        innerbiali(node.left)
        innerbiali(node.right)
        res_list.append(node.val)
    innerbiali(root)
    return res_list

def zhongxubianli(root:TreeNode)->list[int]:
    res_list=[]
    def innerbianli(node:TreeNode):
        if node is None:
            return
        innerbianli(node.left)
        res_list.append(node.val)
        innerbianli(node.right)
    innerbianli(root)
    return res_list

def qianxubianli(root:TreeNode)->list[int]:
    res_list=[]
    def innerbianli(root:TreeNode):
        if root is None:
            return
        res_list.append(root.val)
        innerbianli(root.left)
        innerbianli(root.right)
    innerbianli(root)
    return res_list






print("给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同"
      "如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=0
        self.left=left
        self.right=right
def xiangtongshu(p:TreeNode,q:TreeNode)->TreeNode:
    if p is None and q is None:
        return True
    elif p is None or q is None or p.val != q.val:
        return False
    return xiangtongshu(p.left,q.left) and xiangtongshu(p.right,q.right)



print("给你一个二叉树的根节点 root ， 检查它是否轴对称")
class TreeNode:
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def zhouduichen(root:TreeNode)->bool:
    def innerzhouduichen(left:TreeNode,right:TreeNode)->bool:
        if left is None and right is None:
            return True
        elif left is None or right is None or left.val != right.val:
            return False
        return innerzhouduichen(left.left,right.right) and innerzhouduichen(left.right,right.left)
    if root is None:
        return False
    else:
        return innerzhouduichen(root.left,root.right)




print("二叉树的最大深度")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def maxDepth(root:TreeNode)->int:
    if root is None:
        return 0
    max_l=maxDepth(root.left)
    max_r=maxDepth(root.right)
    return max(max_r,max_l)+1



print("生成杨辉三角的前n行")
def generate(numRows:int) ->list[list[int]]:
    source_list = [[1]*(n+1) for n in range(0,numRows)]
    for i in range(2,numRows):
        for j in range(1,len(source_list[i])-1):
            source_list[i][j] = source_list[i-1][j-1]+source_list[i-1][j]
    print(source_list)
    return source_list
print(generate(5))

print("给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行")
def getRow(rowIndex:int) -> list[int]:
    source_list = [[1]*(r+1)for r in range(0,rowIndex+1)]
    for i in range(2,rowIndex+1):
        for j in range(1,len(source_list[i])-1):
            source_list[i][j] = source_list[i-1][j-1]+source_list[i-1][j]
    return source_list[rowIndex]




print("买卖股票的最佳时机")
def maxProfit(prices:list[int]):
    profit = 0
    min_price=prices[0]
    for p in prices[1::]:
        min_price = min(min_price,p)
        profit = max(profit,p - min_price)
    return profit



print("验证回文串 只取字符串中的字符和数字并转化为小写")
def isHuiWenChuan(s:str) ->bool:
    res = []
    for ss in s:
        if ss.isdigit():
            res.append(ss)
        if ss.isalpha():
            res.append(ss.lower())
    return res == res[::-1]


print("给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素")
def singleNumber(nums:list[int])->int:
    import collections
    res_dic = dict(collections.Counter(nums))
    for k,v in res_dic.items():
        if v == 1:
            return k




print("相交链表"
      "给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。")
class ListNode:
    def __init__(self,val,next=None):
        self.val = val
        self.next = next
def getIntersectionNode(headA:ListNode,headB:ListNode) ->ListNode:
    if headB is None or headA is None:
        return None
    list_a = []
    current = headA
    while current:
        list_a.append(current)
        current=current.next
    current = headB
    while current:
        if current in list_a:
            return current
        current = current.next
    return None



print("给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称")
def convertToTitle(columnNumber:int) ->str:
    res = []
    while columnNumber>0:
        columnNumber = columnNumber -1
        res.append(chr(columnNumber%26+ord("A")))
        columnNumber = columnNumber//26
    return "".join(res[::-1])




print("给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素")
def majorElement(nums:list[int]) -> int:
    import collections
    dicts = dict(collections.Counter(nums))
    tem = len(nums)/2
    for k,v in dicts.items():
        if v>tem:
            return k
majorElement([1,2,3,2])



print("给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号")
def titleToNumber(columnTitle:str) ->int:
    tem = 0
    for column in columnTitle:
        # 满26进一，遍历一次表示未满26，遍历两次，表示满了n个26，看第一位字符是什么
        tem = tem*26+(ord(column)-64)
    return tem


print("编写一个算法来判断一个数 n 是不是快乐数")
def isHappy(n:int)->bool:
    tem_list = []
    while True:
        res = 0
        for i in str(n):
            res = res + int(i)**2
        if res == 1:
            return True
        if res in tem_list:
            return False
        tem_list.append(res)
        n=res

print("给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def removeElements(head:ListNode,val:int)->ListNode:
    if head is None:
        return head
    new_head = ListNode()
    new_head.next = head
    current = new_head
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return new_head.next




print("反转链表")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def fanzhuanlianbiao(head:ListNode)->ListNode:
    if head is None:
        return None
    pre = None
    current = head
    while current:
        temp = current.next
        current.next = pre
        pre = current
        current = temp
    return pre


print("判断是否存在重复元素")
def containDuplicate(self,nums):
    return not len(set(nums)) == len(nums)


print("判断是不是回文链表")
class ListNode:
    def __init__(self,val,next=None):
        self.val=val
        self.next=next
def isHuiwenLianBiao(head:ListNode)->bool:
    temp=[]
    if head is None:
        return False
    current = head
    while current:
        temp.append(current.val)
        current = current.next
    return temp == temp[::-1]

print("给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数")
def missingNumber(nums:list[int]) ->int:
    for n in range(0,len(nums)+1):
        if n not in nums:
            return n

print("给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序")
def moveZeroes(nums:list):
    count = nums.count(0)
    for i in range(0,count):
        nums.remove(0)
        nums.append(0)


print("给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false")
def isPowerOfThree(n:int)->bool:
    if n==0:
        return False
    if n==1:
        return True
    if n==2:
        return False
    res = 1
    while True:
        res = res*3
        if res==n:
            return True
        if res > n:
            return False


print("不使用切片反转字符串")
def reverseString(s:list[str]):
    for i in range(0,len(s)//2):
        temp =s[i]
        s[i]=s[len(s)-1-i]
        s[len(s)-1-i]=temp



print("给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，"
      "应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。")
def intersect(nums1:list,nums2:list)->list[int]:
    import collections
    return list(((collections.Counter(nums1))&(collections.Counter(nums2))).elements())


print("给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1")
def firstUniquChar(s:str)->int:
    # for i in range(0,len(s)):
    #     if s.count(s[i]) == 1:
    #         return i
    # return -1
    import collections
    ds = collections.Counter(s)
    for k,v in enumerate(s):
        if ds[v] == 1:
            return k
    return -1




print("给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果")
def addDigits(num:int) -> int:
    while num>=10:
        a = num//10
        b = num%10
        num = a+b
    return num